Paper 2012/071

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer

Abstract

Succinct arguments for NP are proof systems that allow a weak verifier to retroactively check computation done by a powerful prover. Constructions of such protocols prove membership in languages consisting of \emph{very large yet succinctly-represented constraint satisfaction problems} that, alas, are unnatural in the sense that the problems that arise in practice are not in such form. For general computation tasks, the most natural representation is typically as random-access machine (RAM) algorithms, because such a representation can be obtained very efficiently by applying a compiler to code written in a high-level programming language. Thus, understanding the efficiency of reductions from RAM computations to other NP-complete problem representations for which succinct arguments (or proofs) are known is a prerequisite to a more complete understanding of the applicability of these arguments. Existing succinct argument constructions rely either on circuit satisfiability or (in PCP-based constructions) on algebraic constraint satisfaction problems. In this paper, we present new and more efficient reductions from RAM (and parallel RAM) computations to both problems that (a) preserve succinctness (i.e., do not ``unroll'' the computation of a machine), (b) preserve zero-knowledge and proof-of-knowledge properties, and (c) enjoy fast and highly-parallelizable algorithms for transforming a witness to the RAM computation into a witness for the corresponding problem. These additional properties are typically not considered in ``classical'' complexity theory but are often required or very desirable in the application of succinct arguments. Fulfilling all these efficiency requirements poses significant technical challenges, and we develop a set of tools (both unconditional and leveraging computational assumptions) for generically and efficiently structuring and arithmetizing RAM computations for use in succinct arguments. More generally, our results can be applied to proof systems for NP relying on the aforementioned problem representations; these include various zero-knowledge proof constructions.

Note: Revised introduction and technical sections.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
delegation of computationsuccinct argumentsrandom-access machinesproba- bilistically checkable proofszero-knowledge proofs
Contact author(s)
alexch @ csail mit edu
History
2012-08-18: revised
2012-02-23: received
See all versions
Short URL
https://ia.cr/2012/071
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/071,
      author = {Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer},
      title = {Fast Reductions from {RAMs} to Delegatable Succinct Constraint Satisfaction Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/071},
      year = {2012},
      url = {https://eprint.iacr.org/2012/071}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.